METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />Workshop on Expanders and derandomization (March 21-25, 2011)<br />Mar 24, 15:00-16:00 - Manor Mendel (Open U. Israel, Raanana)<br />Expanders families and Poincaré inequalities<br />---<br />The Poincaré inequality for a regular graph G=(V,E) says that in any mapping of the vertices into the real line f:V-->R, the average over all pairs x,y in V of |f(x)-f(y)|^2 is bounded from above by the average over all edges (x,y) in E of |f(x)-f(y)|^2 times reciprocal of the normalized spectral gap of G.<br /><br />Motivated by its applications for proving non-embeddability results of expanders, Matousek extended the Poincaré inequality for graphs to L_p codomains, p
